// © 2016 and later: Unicode, Inc. and others.
// License & terms of use: http://www.unicode.org/copyright.html
/*
 **********************************************************************
 *   Copyright (c) 2002-2016, International Business Machines
 *   Corporation and others.  All Rights Reserved.
 **********************************************************************
 */

package com.ibm.icu.text;

import com.ibm.icu.impl.Assert;
import com.ibm.icu.impl.RBBIDataWrapper;
import com.ibm.icu.text.RBBIRuleBuilder.IntPair;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;

/**
 * This class is part of the RBBI rule compiler. It builds the state transition table used by the
 * RBBI runtime from the expression syntax tree generated by the rule scanner.
 *
 * <p>This class is part of the RBBI implementation only. There is no user-visible public API here.
 */
class RBBITableBuilder {

    //
    //  RBBIStateDescriptor - The DFA is initially constructed as a set of these descriptors,
    //                        one for each state.
    static class RBBIStateDescriptor {
        boolean fMarked;
        int fAccepting;
        int fLookAhead;
        SortedSet<Integer> fTagVals;
        int fTagsIdx;
        Set<RBBINode> fPositions; // Set of parse tree positions associated
        //   with this state.  Unordered (it's a set).
        //   UVector contents are RBBINode *

        int[] fDtran; // Transitions out of this state.

        //   indexed by input character
        //   contents is int index of dest state
        //   in RBBITableBuilder.fDStates

        RBBIStateDescriptor(int maxInputSymbol) {
            fTagVals = new TreeSet<>();
            fPositions = new HashSet<>();
            fDtran = new int[maxInputSymbol + 1]; // fDtran needs to be pre-sized.
            //   It is indexed by input symbols, and will
            //   hold  the next state number for each
            //   symbol.
        }
    }

    private RBBIRuleBuilder fRB;

    /** The array index into RBBIRuleBuilder.fTreeRoots for the parse tree to operate on. */
    private int fRootIx;

    /** D states (Aho's terminology). Index is state number. */
    private List<RBBIStateDescriptor> fDStates;

    /** Synthesized safe table, a List of row arrays. */
    private List<short[]> fSafeTable;

    private static final int MAX_STATE_FOR_8BITS_TABLE = 255;

    /** Map from rule number (fVal in look ahead nodes) to sequential lookahead index. */
    int[] fLookAheadRuleMap;

    /**
     * Counter used when assigning lookahead rule numbers. Contains the last look-ahead number
     * already in use. The first look-ahead number is 2; Number 1 (ACCEPTING_UNCONDITIONAL) is
     * reserved for non-lookahead accepting states. See the declarations of RBBIStateTableRowT.
     */
    int fLASlotsInUse = RBBIDataWrapper.ACCEPTING_UNCONDITIONAL;

    // -----------------------------------------------------------------------------
    //
    //  Constructor    for RBBITableBuilder.
    //
    //                 rootNode is an index into the array of root nodes that is held by
    //                          the overall RBBIRuleBuilder.
    // -----------------------------------------------------------------------------
    RBBITableBuilder(RBBIRuleBuilder rb, int rootNodeIx) {
        fRootIx = rootNodeIx;
        fRB = rb;
        fDStates = new ArrayList<>();
    }

    // -----------------------------------------------------------------------------
    //
    //   RBBITableBuilder::buildForwardTable  -  This is the main function for building
    //                          the DFA state transition table from the RBBI rules parse tree.
    //
    // -----------------------------------------------------------------------------
    void buildForwardTable() {
        // If there were no rules, just return.  This situation can easily arise
        //   for the reverse rules.
        if (fRB.fTreeRoots[fRootIx] == null) {
            return;
        }

        //
        // Walk through the tree, replacing any references to $variables with a copy of the
        //   parse tree for the substitution expression.
        //
        fRB.fTreeRoots[fRootIx] = fRB.fTreeRoots[fRootIx].flattenVariables(0);
        if (fRB.fDebugEnv != null && fRB.fDebugEnv.indexOf("ftree") >= 0) {
            System.out.println("Parse tree after flattening variable references.");
            fRB.fTreeRoots[fRootIx].printTree(true);
        }

        //
        // If the rules contained any references to {bof}
        //   add a {bof} <cat> <former root of tree> to the
        //   tree.  Means that all matches must start out with the
        //   {bof} fake character.
        //
        if (fRB.fSetBuilder.sawBOF()) {
            RBBINode bofTop = new RBBINode(RBBINode.opCat);
            RBBINode bofLeaf = new RBBINode(RBBINode.leafChar);
            bofTop.fLeftChild = bofLeaf;
            bofTop.fRightChild = fRB.fTreeRoots[fRootIx];
            bofLeaf.fParent = bofTop;
            bofLeaf.fVal = 2; // Reserved value for {bof}.
            fRB.fTreeRoots[fRootIx] = bofTop;
        }

        //
        // Add a unique right-end marker to the expression.
        //   Appears as a cat-node, left child being the original tree,
        //   right child being the end marker.
        //
        RBBINode cn = new RBBINode(RBBINode.opCat);
        cn.fLeftChild = fRB.fTreeRoots[fRootIx];
        fRB.fTreeRoots[fRootIx].fParent = cn;
        RBBINode endMarkerNode = cn.fRightChild = new RBBINode(RBBINode.endMark);
        cn.fRightChild.fParent = cn;
        fRB.fTreeRoots[fRootIx] = cn;

        //
        //  Replace all references to UnicodeSets with the tree for the equivalent
        //      expression.
        //
        fRB.fTreeRoots[fRootIx].flattenSets();
        if (fRB.fDebugEnv != null && fRB.fDebugEnv.indexOf("stree") >= 0) {
            System.out.println("Parse tree after flattening Unicode Set references.");
            fRB.fTreeRoots[fRootIx].printTree(true);
        }

        //
        // calculate the functions nullable, firstpos, lastpos and followpos on
        // nodes in the parse tree.
        //    See the algorithm description in Aho.
        //    Understanding how this works by looking at the code alone will be
        //       nearly impossible.
        //
        calcNullable(fRB.fTreeRoots[fRootIx]);
        calcFirstPos(fRB.fTreeRoots[fRootIx]);
        calcLastPos(fRB.fTreeRoots[fRootIx]);
        calcFollowPos(fRB.fTreeRoots[fRootIx]);
        if (fRB.fDebugEnv != null && fRB.fDebugEnv.indexOf("pos") >= 0) {
            System.out.print("\n");
            printPosSets(fRB.fTreeRoots[fRootIx]);
        }

        //
        //  For "chained" rules, modify the followPos sets
        //
        if (fRB.fChainRules) {
            calcChainedFollowPos(fRB.fTreeRoots[fRootIx], endMarkerNode);
        }

        //
        //  BOF (start of input) test fixup.
        //
        if (fRB.fSetBuilder.sawBOF()) {
            bofFixup();
        }

        //
        // Build the DFA state transition tables.
        //
        buildStateTable();
        mapLookAheadRules();
        flagAcceptingStates();
        flagLookAheadStates();
        flagTaggedStates();

        //
        // Update the global table of rule status {tag} values
        // The rule builder has a global vector of status values that are common
        //    for all tables.  Merge the ones from this table into the global set.
        //
        mergeRuleStatusVals();
    }

    // -----------------------------------------------------------------------------
    //
    //   calcNullable.    Impossible to explain succinctly.  See Aho, section 3.9
    //
    // -----------------------------------------------------------------------------
    void calcNullable(RBBINode n) {
        if (n == null) {
            return;
        }
        if (n.fType == RBBINode.setRef || n.fType == RBBINode.endMark) {
            // These are non-empty leaf node types.
            n.fNullable = false;
            return;
        }

        if (n.fType == RBBINode.lookAhead || n.fType == RBBINode.tag) {
            // Lookahead marker node.  It's a leaf, so no recursion on children.
            // It's nullable because it does not match any literal text from the input stream.
            n.fNullable = true;
            return;
        }

        // The node is not a leaf.
        //  Calculate nullable on its children.
        calcNullable(n.fLeftChild);
        calcNullable(n.fRightChild);

        // Apply functions from table 3.40 in Aho
        if (n.fType == RBBINode.opOr) {
            n.fNullable = n.fLeftChild.fNullable || n.fRightChild.fNullable;
        } else if (n.fType == RBBINode.opCat) {
            n.fNullable = n.fLeftChild.fNullable && n.fRightChild.fNullable;
        } else if (n.fType == RBBINode.opStar || n.fType == RBBINode.opQuestion) {
            n.fNullable = true;
        } else {
            n.fNullable = false;
        }
    }

    // -----------------------------------------------------------------------------
    //
    //   calcFirstPos.    Impossible to explain succinctly.  See Aho, section 3.9
    //
    // -----------------------------------------------------------------------------
    void calcFirstPos(RBBINode n) {
        if (n == null) {
            return;
        }
        if (n.fType == RBBINode.leafChar
                || n.fType == RBBINode.endMark
                || n.fType == RBBINode.lookAhead
                || n.fType == RBBINode.tag) {
            // These are non-empty leaf node types.
            n.fFirstPosSet.add(n);
            return;
        }

        // The node is not a leaf.
        //  Calculate firstPos on its children.
        calcFirstPos(n.fLeftChild);
        calcFirstPos(n.fRightChild);

        // Apply functions from table 3.40 in Aho
        if (n.fType == RBBINode.opOr) {
            n.fFirstPosSet.addAll(n.fLeftChild.fFirstPosSet);
            n.fFirstPosSet.addAll(n.fRightChild.fFirstPosSet);
        } else if (n.fType == RBBINode.opCat) {
            n.fFirstPosSet.addAll(n.fLeftChild.fFirstPosSet);
            if (n.fLeftChild.fNullable) {
                n.fFirstPosSet.addAll(n.fRightChild.fFirstPosSet);
            }
        } else if (n.fType == RBBINode.opStar
                || n.fType == RBBINode.opQuestion
                || n.fType == RBBINode.opPlus) {
            n.fFirstPosSet.addAll(n.fLeftChild.fFirstPosSet);
        }
    }

    // -----------------------------------------------------------------------------
    //
    //   calcLastPos.    Impossible to explain succinctly.  See Aho, section 3.9
    //
    // -----------------------------------------------------------------------------
    void calcLastPos(RBBINode n) {
        if (n == null) {
            return;
        }
        if (n.fType == RBBINode.leafChar
                || n.fType == RBBINode.endMark
                || n.fType == RBBINode.lookAhead
                || n.fType == RBBINode.tag) {
            // These are non-empty leaf node types.
            n.fLastPosSet.add(n);
            return;
        }

        // The node is not a leaf.
        //  Calculate lastPos on its children.
        calcLastPos(n.fLeftChild);
        calcLastPos(n.fRightChild);

        // Apply functions from table 3.40 in Aho
        if (n.fType == RBBINode.opOr) {
            n.fLastPosSet.addAll(n.fLeftChild.fLastPosSet);
            n.fLastPosSet.addAll(n.fRightChild.fLastPosSet);
        } else if (n.fType == RBBINode.opCat) {
            n.fLastPosSet.addAll(n.fRightChild.fLastPosSet);
            if (n.fRightChild.fNullable) {
                n.fLastPosSet.addAll(n.fLeftChild.fLastPosSet);
            }
        } else if (n.fType == RBBINode.opStar
                || n.fType == RBBINode.opQuestion
                || n.fType == RBBINode.opPlus) {
            n.fLastPosSet.addAll(n.fLeftChild.fLastPosSet);
        }
    }

    // -----------------------------------------------------------------------------
    //
    //   calcFollowPos.    Impossible to explain succinctly.  See Aho, section 3.9
    //
    // -----------------------------------------------------------------------------
    void calcFollowPos(RBBINode n) {
        if (n == null || n.fType == RBBINode.leafChar || n.fType == RBBINode.endMark) {
            return;
        }

        calcFollowPos(n.fLeftChild);
        calcFollowPos(n.fRightChild);

        // Aho rule #1
        if (n.fType == RBBINode.opCat) {
            for (RBBINode i /* is 'i' in Aho's description */ : n.fLeftChild.fLastPosSet) {
                i.fFollowPos.addAll(n.fRightChild.fFirstPosSet);
            }
        }

        // Aho rule #2
        if (n.fType == RBBINode.opStar || n.fType == RBBINode.opPlus) {
            for (RBBINode i /* again, n and i are the names from Aho's description */ :
                    n.fLastPosSet) {
                i.fFollowPos.addAll(n.fFirstPosSet);
            }
        }
    }

    // -----------------------------------------------------------------------------
    //
    //           addRuleRootNodes    Recursively walk a parse tree, adding all nodes flagged
    //                               as roots of a rule to a destination vector.
    //
    // -----------------------------------------------------------------------------
    void addRuleRootNodes(List<RBBINode> dest, RBBINode node) {
        if (node == null) {
            return;
        }
        if (node.fRuleRoot) {
            dest.add(node);
            // Note: rules cannot nest. If we found a rule start node,
            //       no child node can also be a start node.
            return;
        }
        addRuleRootNodes(dest, node.fLeftChild);
        addRuleRootNodes(dest, node.fRightChild);
    }

    // -----------------------------------------------------------------------------
    //
    //   calcChainedFollowPos.    Modify the previously calculated followPos sets
    //                            to implement rule chaining.  NOT described by Aho
    //
    // -----------------------------------------------------------------------------
    void calcChainedFollowPos(RBBINode tree, RBBINode endMarkNode) {

        List<RBBINode> leafNodes = new ArrayList<>();

        // get a list all leaf nodes
        tree.findNodes(leafNodes, RBBINode.leafChar);

        // Collect all leaf nodes that can start matches for rules
        // with inbound chaining enabled, which is the union of the
        // firstPosition sets from each of the rule root nodes.

        List<RBBINode> ruleRootNodes = new ArrayList<>();
        addRuleRootNodes(ruleRootNodes, tree);

        Set<RBBINode> matchStartNodes = new HashSet<>();
        for (RBBINode node : ruleRootNodes) {
            if (node.fChainIn) {
                matchStartNodes.addAll(node.fFirstPosSet);
            }
        }

        // Iterate over all leaf nodes,
        //
        for (RBBINode endNode : leafNodes) {

            // Identify leaf nodes that correspond to overall rule match positions.
            //   These include the endMarkNode in their followPos sets.
            //
            // Note: do not consider other end marker nodes, those that are added to
            //       look-ahead rules. These can't chain; a match immediately stops
            //       further matching. This leaves exactly one end marker node, the one
            //       at the end of the complete tree.

            if (!endNode.fFollowPos.contains(endMarkNode)) {
                continue;
            }

            // We've got a node that can end a match.

            // Now iterate over the nodes that can start a match, looking for ones
            //   with the same char class as our ending node.
            for (RBBINode startNode : matchStartNodes) {
                if (startNode.fType != RBBINode.leafChar) {
                    continue;
                }

                if (endNode.fVal == startNode.fVal) {
                    // The end val (character class) of one possible match is the
                    //   same as the start of another.

                    // Add all nodes from the followPos of the start node to the
                    //  followPos set of the end node, which will have the effect of
                    //  letting matches transition from a match state at endNode
                    //  to the second char of a match starting with startNode.
                    endNode.fFollowPos.addAll(startNode.fFollowPos);
                }
            }
        }
    }

    // -----------------------------------------------------------------------------
    //
    //   bofFixup.    Fixup for state tables that include {bof} beginning of input testing.
    //                Do an swizzle similar to chaining, modifying the followPos set of
    //                the bofNode to include the followPos nodes from other {bot} nodes
    //                scattered through the tree.
    //
    //                This function has much in common with calcChainedFollowPos().
    //
    // -----------------------------------------------------------------------------
    void bofFixup() {
        //
        //   The parse tree looks like this ...
        //         fTree root  --.       <cat>
        //                               /     \
        //                            <cat>   <#end node>
        //                           /     \
        //                     <bofNode>   rest
        //                               of tree
        //
        //    We will be adding things to the followPos set of the <bofNode>
        //
        RBBINode bofNode = fRB.fTreeRoots[fRootIx].fLeftChild.fLeftChild;
        Assert.assrt(bofNode.fType == RBBINode.leafChar);
        Assert.assrt(bofNode.fVal == 2);

        // Get all nodes that can be the start a match of the user-written rules
        //  (excluding the fake bofNode)
        //  We want the nodes that can start a match in the
        //     part labeled "rest of tree"
        //
        Set<RBBINode> matchStartNodes = fRB.fTreeRoots[fRootIx].fLeftChild.fRightChild.fFirstPosSet;
        for (RBBINode startNode : matchStartNodes) {
            if (startNode.fType != RBBINode.leafChar) {
                continue;
            }

            if (startNode.fVal == bofNode.fVal) {
                //  We found a leaf node corresponding to a {bof} that was
                //    explicitly written into a rule.
                //  Add everything from the followPos set of this node to the
                //    followPos set of the fake bofNode at the start of the tree.
                //
                bofNode.fFollowPos.addAll(startNode.fFollowPos);
            }
        }
    }

    // -----------------------------------------------------------------------------
    //
    //   buildStateTable()    Determine the set of runtime DFA states and the
    //                        transition tables for these states, by the algorithm
    //                        of fig. 3.44 in Aho.
    //
    //                        Most of the comments are quotes of Aho's psuedo-code.
    //
    // -----------------------------------------------------------------------------
    void buildStateTable() {
        //
        // Add a dummy state 0 - the stop state.  Not from Aho.
        int lastInputSymbol = fRB.fSetBuilder.getNumCharCategories() - 1;
        RBBIStateDescriptor failState = new RBBIStateDescriptor(lastInputSymbol);
        fDStates.add(failState);

        // initially, the only unmarked state in Dstates is firstpos(root),
        //       where toot is the root of the syntax tree for (r)#;
        RBBIStateDescriptor initialState = new RBBIStateDescriptor(lastInputSymbol);
        initialState.fPositions.addAll(fRB.fTreeRoots[fRootIx].fFirstPosSet);
        fDStates.add(initialState);

        // while there is an unmarked state T in Dstates do begin
        for (; ; ) {
            RBBIStateDescriptor T = null;
            int tx;
            for (tx = 1; tx < fDStates.size(); tx++) {
                RBBIStateDescriptor temp = fDStates.get(tx);
                if (temp.fMarked == false) {
                    T = temp;
                    break;
                }
            }
            if (T == null) {
                break;
            }

            // mark T;
            T.fMarked = true;

            // for each input symbol a do begin
            int a;
            for (a = 1; a <= lastInputSymbol; a++) {
                // let U be the set of positions that are in followpos(p)
                //    for some position p in T
                //    such that the symbol at position p is a;
                Set<RBBINode> U = null;
                for (RBBINode p : T.fPositions) {
                    if ((p.fType == RBBINode.leafChar) && (p.fVal == a)) {
                        if (U == null) {
                            U = new HashSet<>();
                        }
                        U.addAll(p.fFollowPos);
                    }
                }

                // if U is not empty and not in DStates then
                int ux = 0;
                boolean UinDstates = false;
                if (U != null) {
                    Assert.assrt(U.size() > 0);
                    int ix;
                    for (ix = 0; ix < fDStates.size(); ix++) {
                        RBBIStateDescriptor temp2;
                        temp2 = fDStates.get(ix);
                        if (U.equals(temp2.fPositions)) {
                            U = temp2.fPositions;
                            ux = ix;
                            UinDstates = true;
                            break;
                        }
                    }

                    // Add U as an unmarked state to Dstates
                    if (!UinDstates) {
                        RBBIStateDescriptor newState = new RBBIStateDescriptor(lastInputSymbol);
                        newState.fPositions = U;
                        fDStates.add(newState);
                        ux = fDStates.size() - 1;
                    }

                    // Dtran[T, a] := U;
                    T.fDtran[a] = ux;
                }
            }
        }
    }

    /** mapLookAheadRules */
    void mapLookAheadRules() {
        fLookAheadRuleMap = new int[fRB.fScanner.numRules() + 1];

        for (RBBIStateDescriptor sd : fDStates) {
            int laSlotForState = 0;

            // Establish the look-ahead slot for this state, if the state covers
            // any look-ahead nodes - corresponding to the '/' in look-ahead rules.

            // If any of the look-ahead nodes already have a slot assigned, use it,
            // otherwise assign a new one.

            boolean sawLookAheadNode = false;
            for (RBBINode node : sd.fPositions) {
                if (node.fType != RBBINode.lookAhead) {
                    continue;
                }
                sawLookAheadNode = true;
                int ruleNum = node.fVal; // Set when rule was originally parsed.
                assert (ruleNum < fLookAheadRuleMap.length);
                assert (ruleNum > 0);
                int laSlot = fLookAheadRuleMap[ruleNum];
                if (laSlot != 0) {
                    if (laSlotForState == 0) {
                        laSlotForState = laSlot;
                    } else {
                        // TODO: figure out if this can fail, change to setting an error code if so.
                        assert (laSlot == laSlotForState);
                    }
                }
            }
            if (!sawLookAheadNode) {
                continue;
            }

            if (laSlotForState == 0) {
                laSlotForState = ++fLASlotsInUse;
            }

            // For each look ahead node covered by this state,
            // set the mapping from the node's rule number to the look ahead slot.
            // There can be multiple nodes/rule numbers going to the same la slot.

            for (RBBINode node : sd.fPositions) {
                if (node.fType != RBBINode.lookAhead) {
                    continue;
                }
                int ruleNum = node.fVal; // Set when rule was originally parsed.
                int existingVal = fLookAheadRuleMap[ruleNum];
                assert (existingVal == 0 || existingVal == laSlotForState);
                fLookAheadRuleMap[ruleNum] = laSlotForState;
            }
        }
    }

    // -----------------------------------------------------------------------------
    //
    //   flagAcceptingStates    Identify accepting states.
    //                          First get a list of all of the end marker nodes.
    //                          Then, for each state s,
    //                              if s contains one of the end marker nodes in its list of tree
    // positions then
    //                                  s is an accepting state.
    //
    // -----------------------------------------------------------------------------
    void flagAcceptingStates() {
        List<RBBINode> endMarkerNodes = new ArrayList<>();
        RBBINode endMarker;
        int i;
        int n;

        fRB.fTreeRoots[fRootIx].findNodes(endMarkerNodes, RBBINode.endMark);

        for (i = 0; i < endMarkerNodes.size(); i++) {
            endMarker = endMarkerNodes.get(i);
            for (n = 0; n < fDStates.size(); n++) {
                RBBIStateDescriptor sd = fDStates.get(n);
                if (sd.fPositions.contains(endMarker)) {
                    // Any non-zero value for fAccepting means this is an accepting node.
                    // The value is what will be returned to the user as the break status.
                    // If no other value was specified, force it to ACCEPTING_UNCONDITIONAL (1).

                    if (sd.fAccepting == 0) {
                        // State hasn't been marked as accepting yet.  Do it now.
                        sd.fAccepting = fLookAheadRuleMap[endMarker.fVal];
                        if (sd.fAccepting == 0) {
                            sd.fAccepting = RBBIDataWrapper.ACCEPTING_UNCONDITIONAL;
                        }
                    }
                    if (sd.fAccepting == RBBIDataWrapper.ACCEPTING_UNCONDITIONAL
                            && endMarker.fVal != 0) {
                        // Both lookahead and non-lookahead accepting for this state.
                        // Favor the look-ahead, because a look-ahead match needs to
                        // immediately stop the run-time engine. First match, not longest.
                        sd.fAccepting = fLookAheadRuleMap[endMarker.fVal];
                    }
                    // implicit else:
                    // if sd.fAccepting already had a value other than 0 or 1, leave it be.
                }
            }
        }
    }

    // -----------------------------------------------------------------------------
    //
    //    flagLookAheadStates   Very similar to flagAcceptingStates, above.
    //
    // -----------------------------------------------------------------------------
    void flagLookAheadStates() {
        List<RBBINode> lookAheadNodes = new ArrayList<>();
        RBBINode lookAheadNode;
        int i;
        int n;

        fRB.fTreeRoots[fRootIx].findNodes(lookAheadNodes, RBBINode.lookAhead);
        for (i = 0; i < lookAheadNodes.size(); i++) {
            lookAheadNode = lookAheadNodes.get(i);
            for (n = 0; n < fDStates.size(); n++) {
                RBBIStateDescriptor sd = fDStates.get(n);
                if (sd.fPositions.contains(lookAheadNode)) {
                    int lookaheadSlot = fLookAheadRuleMap[lookAheadNode.fVal];
                    assert (sd.fLookAhead == 0 || sd.fLookAhead == lookaheadSlot);
                    sd.fLookAhead = lookaheadSlot;
                }
            }
        }
    }

    // -----------------------------------------------------------------------------
    //
    //    flagTaggedStates
    //
    // -----------------------------------------------------------------------------
    void flagTaggedStates() {
        List<RBBINode> tagNodes = new ArrayList<>();
        RBBINode tagNode;
        int i;
        int n;

        fRB.fTreeRoots[fRootIx].findNodes(tagNodes, RBBINode.tag);
        for (i = 0; i < tagNodes.size(); i++) { // For each tag node t (all of 'em)
            tagNode = tagNodes.get(i);

            for (n = 0; n < fDStates.size(); n++) { //    For each state  s (row in the state table)
                RBBIStateDescriptor sd = fDStates.get(n);
                if (sd.fPositions.contains(tagNode)) { //       if  s include the tag node t
                    sd.fTagVals.add(tagNode.fVal);
                }
            }
        }
    }

    // -----------------------------------------------------------------------------
    //
    //  mergeRuleStatusVals
    //
    //      Allocate positions in the  global array of rule status {tag} values
    //
    //      The RBBI runtime uses an array of {sets of status values} that can
    //      be returned for boundaries.  Each accepting state that has non-zero
    //      status includes an index into this array.  The format of the array
    //      is
    //           Num of status values in group 1
    //              status val
    //              status val
    //              ...
    //           Num of status vals in group 2
    //              status val
    //              status val
    //              ...
    //           etc.
    //
    //
    // -----------------------------------------------------------------------------

    void mergeRuleStatusVals() {
        //
        //  The basic outline of what happens here is this...
        //
        //    for each state in this state table
        //       if the status tag list for this state is in the global statuses list
        //           record where and
        //           continue with the next state
        //       else
        //           add the tag list for this state to the global list.
        //
        int n;

        // Pre-load a single tag of {0} into the table.
        //   We will need this as a default, for rule sets with no explicit tagging,
        //   or with explicit tagging of {0}.
        if (fRB.fRuleStatusVals.size() == 0) {
            fRB.fRuleStatusVals.add(1); // Num of statuses in group
            fRB.fRuleStatusVals.add(0); //   and our single status of zero

            SortedSet<Integer> s0 = new TreeSet<>(); // mapping for rules with no explicit tagging
            fRB.fStatusSets.put(s0, 0); //   (key is an empty set).

            SortedSet<Integer> s1 =
                    new TreeSet<>(); // mapping for rules with explicit tagging of {0}
            s1.add(0);
            fRB.fStatusSets.put(s1, 0);
        }

        //    For each state, check whether the state's status tag values are
        //       already entered into the status values array, and add them if not.
        for (n = 0; n < fDStates.size(); n++) {
            RBBIStateDescriptor sd = fDStates.get(n);
            Set<Integer> statusVals = sd.fTagVals;
            Integer arrayIndexI = fRB.fStatusSets.get(statusVals);
            if (arrayIndexI == null) {
                // This is the first encounter of this set of status values.
                //   Add them to the statusSets map, This map associates
                //   the set of status values with an index in the runtime status
                //   values array.
                arrayIndexI = fRB.fRuleStatusVals.size();
                fRB.fStatusSets.put(statusVals, arrayIndexI);

                // Add the new set of status values to the vector of values that
                //   will eventually become the array used by the runtime engine.
                fRB.fRuleStatusVals.add(statusVals.size());
                fRB.fRuleStatusVals.addAll(statusVals);
            }

            // Save the runtime array index back into the state descriptor.
            sd.fTagsIdx = arrayIndexI.intValue();
        }
    }

    // -----------------------------------------------------------------------------
    //
    //  printPosSets   Debug function.  Dump Nullable, firstpos, lastpos and followpos
    //                 for each node in the tree.
    //
    // -----------------------------------------------------------------------------

    void printPosSets(RBBINode n) {
        if (n == null) {
            return;
        }
        RBBINode.printNode(n);
        System.out.print("         Nullable:  " + n.fNullable);

        System.out.print("         firstpos:  ");
        printSet(n.fFirstPosSet);

        System.out.print("         lastpos:   ");
        printSet(n.fLastPosSet);

        System.out.print("         followpos: ");
        printSet(n.fFollowPos);

        printPosSets(n.fLeftChild);
        printPosSets(n.fRightChild);
    }

    /**
     * Find duplicate (redundant) character classes. Begin looking with categories.first.
     * Duplicates, if found are returned in the categories parameter. This is an iterator-like
     * function, used to identify character classes (state table columns) that can be eliminated.
     *
     * @param categories in/out parameter, specifies where to start looking for duplicates, and
     *     returns the first pair of duplicates found, if any.
     * @return true if duplicate char classes were found, false otherwise.
     * @internal
     */
    boolean findDuplCharClassFrom(RBBIRuleBuilder.IntPair categories) {
        int numStates = fDStates.size();
        int numCols = fRB.fSetBuilder.getNumCharCategories();

        int table_base = 0;
        int table_dupl = 0;
        for (; categories.first < numCols - 1; ++categories.first) {
            // Note: dictionary & non-dictionary columns cannot be merged.
            //       The limitSecond value prevents considering mixed pairs.
            //       Dictionary categories are >= DictCategoriesStart.
            //       Non dict categories are   <  DictCategoriesStart.
            int limitSecond =
                    categories.first < fRB.fSetBuilder.getDictCategoriesStart()
                            ? fRB.fSetBuilder.getDictCategoriesStart()
                            : numCols;
            for (categories.second = categories.first + 1;
                    categories.second < limitSecond;
                    ++categories.second) {
                for (int state = 0; state < numStates; state++) {
                    RBBIStateDescriptor sd = fDStates.get(state);
                    table_base = sd.fDtran[categories.first];
                    table_dupl = sd.fDtran[categories.second];
                    if (table_base != table_dupl) {
                        break;
                    }
                }
                if (table_base == table_dupl) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * Remove a column from the state table. Used when two character categories have been found
     * equivalent, and merged together, to eliminate the unneeded table column.
     */
    void removeColumn(int column) {
        int numStates = fDStates.size();
        for (int state = 0; state < numStates; state++) {
            RBBIStateDescriptor sd = fDStates.get(state);
            assert (column < sd.fDtran.length);
            int[] newArray = Arrays.copyOf(sd.fDtran, sd.fDtran.length - 1);
            System.arraycopy(sd.fDtran, column + 1, newArray, column, newArray.length - column);
            sd.fDtran = newArray;
        }
    }

    /**
     * Find duplicate (redundant) states, beginning at the specified pair, within this state table.
     * This is an iterator-like function, used to identify states (state table rows) that can be
     * eliminated.
     *
     * @param states in/out parameter, specifies where to start looking for duplicates, and returns
     *     the first pair of duplicates found, if any.
     * @return true if duplicate states were found, false otherwise.
     * @internal
     */
    boolean findDuplicateState(RBBIRuleBuilder.IntPair states) {
        int numStates = fDStates.size();
        int numCols = fRB.fSetBuilder.getNumCharCategories();

        for (; states.first < numStates - 1; ++states.first) {
            RBBIStateDescriptor firstSD = fDStates.get(states.first);
            for (states.second = states.first + 1; states.second < numStates; ++states.second) {
                RBBIStateDescriptor duplSD = fDStates.get(states.second);
                if (firstSD.fAccepting != duplSD.fAccepting
                        || firstSD.fLookAhead != duplSD.fLookAhead
                        || firstSD.fTagsIdx != duplSD.fTagsIdx) {
                    continue;
                }
                boolean rowsMatch = true;
                for (int col = 0; col < numCols; ++col) {
                    int firstVal = firstSD.fDtran[col];
                    int duplVal = duplSD.fDtran[col];
                    if (!((firstVal == duplVal)
                            || ((firstVal == states.first || firstVal == states.second)
                                    && (duplVal == states.first || duplVal == states.second)))) {
                        rowsMatch = false;
                        break;
                    }
                }
                if (rowsMatch) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * Find the next duplicate state in the safe reverse table. An iterator function.
     *
     * @param states in/out parameter, specifies where to start looking for duplicates, and returns
     *     the first pair of duplicates found, if any.
     * @return true if duplicate states were found, false otherwise.
     * @internal
     */
    boolean findDuplicateSafeState(RBBIRuleBuilder.IntPair states) {
        int numStates = fSafeTable.size();

        for (; states.first < numStates - 1; ++states.first) {
            short[] firstRow = fSafeTable.get(states.first);
            for (states.second = states.first + 1; states.second < numStates; ++states.second) {
                short[] duplRow = fSafeTable.get(states.second);
                boolean rowsMatch = true;
                int numCols = firstRow.length;
                for (int col = 0; col < numCols; ++col) {
                    int firstVal = firstRow[col];
                    int duplVal = duplRow[col];
                    if (!((firstVal == duplVal)
                            || ((firstVal == states.first || firstVal == states.second)
                                    && (duplVal == states.first || duplVal == states.second)))) {
                        rowsMatch = false;
                        break;
                    }
                }
                if (rowsMatch) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * Remove a duplicate state (row) from the state table. All references to the deleted (second)
     * state are redirected to first state.
     *
     * @param duplStates The duplicate pair of states.
     * @internal
     */
    void removeState(IntPair duplStates) {
        final int keepState = duplStates.first;
        final int duplState = duplStates.second;
        assert (keepState < duplState);
        assert (duplState < fDStates.size());

        fDStates.remove(duplState);

        int numStates = fDStates.size();
        int numCols = fRB.fSetBuilder.getNumCharCategories();
        for (int state = 0; state < numStates; ++state) {
            RBBIStateDescriptor sd = fDStates.get(state);
            for (int col = 0; col < numCols; col++) {
                int existingVal = sd.fDtran[col];
                int newVal = existingVal;
                if (existingVal == duplState) {
                    newVal = keepState;
                } else if (existingVal > duplState) {
                    newVal = existingVal - 1;
                }
                sd.fDtran[col] = newVal;
            }
        }
    }

    /**
     * Remove a duplicate state from the safe table.
     *
     * @param duplStates The duplicate pair of states. The first is kept, the second is removed. All
     *     references to the second in the state table are retargeted to the first.
     * @internal
     */
    void removeSafeState(IntPair duplStates) {
        final int keepState = duplStates.first;
        final int duplState = duplStates.second;
        assert (keepState < duplState);
        assert (duplState < fSafeTable.size());

        fSafeTable.remove(duplState);
        int numStates = fSafeTable.size();
        for (int state = 0; state < numStates; ++state) {
            short[] row = fSafeTable.get(state);
            for (int col = 0; col < row.length; col++) {
                int existingVal = row[col];
                int newVal = existingVal;
                if (existingVal == duplState) {
                    newVal = keepState;
                } else if (existingVal > duplState) {
                    newVal = existingVal - 1;
                }
                row[col] = (short) newVal;
            }
        }
    }

    /**
     * Check for, and remove duplicate states (table rows).
     *
     * @return the number of states removed.
     * @internal
     */
    int removeDuplicateStates() {
        IntPair dupls = new IntPair(3, 0);
        int numStatesRemoved = 0;

        while (findDuplicateState(dupls)) {
            // System.out.printf("Removing duplicate states (%d, %d)\n", dupls.first, dupls.second);
            removeState(dupls);
            ++numStatesRemoved;
        }
        return numStatesRemoved;
    }

    /**
     * Calculate the size in bytes of the serialized form of this state transition table, which is
     * identical to the ICU4C runtime form. Refer to common/rbbidata.h from ICU4C for the
     * declarations of the structures being matched by this calculation.
     */
    int getTableSize() {
        if (fRB.fTreeRoots[fRootIx] == null) {
            return 0;
        }
        int size =
                RBBIDataWrapper.RBBIStateTable
                        .fHeaderSize; // The header, with no rows to the table.
        int numRows = fDStates.size();
        int numCols = fRB.fSetBuilder.getNumCharCategories();
        boolean use8Bits = numRows <= MAX_STATE_FOR_8BITS_TABLE;
        int rowSize = (use8Bits ? 1 : 2) * (RBBIDataWrapper.NEXTSTATES + numCols);
        size += numRows * rowSize;
        size = (size + 7) & ~7; // round up to a multiple of 8 bytes
        return size;
    }

    /**
     * Create a RBBIDataWrapper.RBBIStateTable for a newly compiled table.
     * RBBIDataWrapper.RBBIStateTable is similar to struct RBBIStateTable in ICU4C, in
     * common/rbbidata.h
     */
    RBBIDataWrapper.RBBIStateTable exportTable() {
        int state;
        int col;

        RBBIDataWrapper.RBBIStateTable table = new RBBIDataWrapper.RBBIStateTable();
        if (fRB.fTreeRoots[fRootIx] == null) {
            return table;
        }

        Assert.assrt(fRB.fSetBuilder.getNumCharCategories() < 0x7fff && fDStates.size() < 0x7fff);
        table.fNumStates = fDStates.size();
        table.fDictCategoriesStart = fRB.fSetBuilder.getDictCategoriesStart();
        table.fLookAheadResultsSize =
                fLASlotsInUse == RBBIDataWrapper.ACCEPTING_UNCONDITIONAL ? 0 : fLASlotsInUse + 1;
        boolean use8Bits = table.fNumStates <= MAX_STATE_FOR_8BITS_TABLE;

        // Size of table size in shorts.
        int rowLen =
                RBBIDataWrapper.NEXTSTATES
                        + fRB.fSetBuilder.getNumCharCategories(); // Row Length in shorts.
        int tableSize;
        if (use8Bits) {
            tableSize =
                    (getTableSize()
                            - RBBIDataWrapper.RBBIStateTable
                                    .fHeaderSize); // fTable length in bytes.
            table.fTable = new char[tableSize];
            table.fRowLen = rowLen; // Row length in bytes.
        } else {
            tableSize =
                    (getTableSize() - RBBIDataWrapper.RBBIStateTable.fHeaderSize)
                            / 2; // fTable length in shorts.
            table.fTable = new char[tableSize];
            table.fRowLen = rowLen * 2; // Row length in bytes.
        }

        if (fRB.fLookAheadHardBreak) {
            table.fFlags |= RBBIDataWrapper.RBBI_LOOKAHEAD_HARD_BREAK;
        }
        if (fRB.fSetBuilder.sawBOF()) {
            table.fFlags |= RBBIDataWrapper.RBBI_BOF_REQUIRED;
        }
        if (use8Bits) {
            table.fFlags |= RBBIDataWrapper.RBBI_8BITS_ROWS;
        }

        int numCharCategories = fRB.fSetBuilder.getNumCharCategories();
        for (state = 0; state < table.fNumStates; state++) {
            RBBIStateDescriptor sd = fDStates.get(state);
            int row = state * rowLen;
            if (use8Bits) {
                Assert.assrt(0 <= sd.fAccepting && sd.fAccepting <= 255);
                Assert.assrt(0 <= sd.fLookAhead && sd.fLookAhead <= 255);
            } else {
                Assert.assrt(0 <= sd.fAccepting && sd.fAccepting <= 0xffff);
                Assert.assrt(0 <= sd.fLookAhead && sd.fLookAhead <= 0xffff);
            }
            table.fTable[row + RBBIDataWrapper.ACCEPTING] = (char) sd.fAccepting;
            table.fTable[row + RBBIDataWrapper.LOOKAHEAD] = (char) sd.fLookAhead;
            table.fTable[row + RBBIDataWrapper.TAGSIDX] = (char) sd.fTagsIdx;
            for (col = 0; col < numCharCategories; col++) {
                if (use8Bits) {
                    Assert.assrt(
                            0 <= sd.fDtran[col] && sd.fDtran[col] <= MAX_STATE_FOR_8BITS_TABLE);
                }
                table.fTable[row + RBBIDataWrapper.NEXTSTATES + col] = (char) sd.fDtran[col];
            }
        }
        return table;
    }

    /** Synthesize a safe state table from the main state table. */
    void buildSafeReverseTable() {
        // Safe Reverse table construction is described in more detail in the corresponding
        // function in ICU4C, in source/common/rbbitblb.cpp. Not duplicated here because
        // it is too likely to get out of sync.

        // Each safe pair is stored as two chars in the safePair stringBuilder.
        StringBuilder safePairs = new StringBuilder();

        int numCharClasses = fRB.fSetBuilder.getNumCharCategories();
        int numStates = fDStates.size();

        for (int c1 = 0; c1 < numCharClasses; ++c1) {
            for (int c2 = 0; c2 < numCharClasses; ++c2) {
                int wantedEndState = -1;
                int endState = 0;
                for (int startState = 1; startState < numStates; ++startState) {
                    RBBIStateDescriptor startStateD = fDStates.get(startState);
                    int s2 = startStateD.fDtran[c1];
                    RBBIStateDescriptor s2StateD = fDStates.get(s2);
                    endState = s2StateD.fDtran[c2];
                    if (wantedEndState < 0) {
                        wantedEndState = endState;
                    } else {
                        if (wantedEndState != endState) {
                            break;
                        }
                    }
                }
                if (wantedEndState == endState) {
                    safePairs.append((char) c1);
                    safePairs.append((char) c2);
                    // System.out.printf("(%d, %d) ", c1, c2);
                }
            }
            // System.out.printf("\n");
        }

        // Populate the initial safe table.
        // The table as a whole is a List<short[]>
        // Row 0 is the stop state.
        // Row 1 is the start sate.
        // Row 2 and beyond are other states, initially one per char class, but
        //   after initial construction, many of the states will be combined, compacting the table.)
        // The String holds the nextState data only. The four leading fields of a row, fAccepting,
        // fLookAhead, etc. are not needed for the safe table, and are omitted at this stage of
        // building.

        assert (fSafeTable == null);
        fSafeTable = new ArrayList<>();
        for (int row = 0; row < numCharClasses + 2; ++row) {
            fSafeTable.add(new short[numCharClasses]);
        }

        // From the start state, each input char class transitions to the state for that input.
        short[] startState = fSafeTable.get(1);
        for (int charClass = 0; charClass < numCharClasses; ++charClass) {
            // Note: +2 to skip the start & stop state rows.
            startState[charClass] = (short) (charClass + 2);
        }

        // Initially make every other state table row look like the start state row
        //    (except for the stop state, which remains all 0)
        for (int row = 2; row < numCharClasses + 2; ++row) {
            System.arraycopy(startState, 0, fSafeTable.get(row), 0, startState.length);
        }

        // Run through the safe pairs, set the next state to zero when pair has been seen.
        // Zero being the stop state, meaning we found a safe point.
        for (int pairIdx = 0; pairIdx < safePairs.length(); pairIdx += 2) {
            int c1 = safePairs.charAt(pairIdx);
            int c2 = safePairs.charAt(pairIdx + 1);

            short[] rowState = fSafeTable.get(c2 + 2);
            rowState[c1] = 0;
        }

        // Remove duplicate or redundant rows from the table.
        RBBIRuleBuilder.IntPair states = new RBBIRuleBuilder.IntPair(1, 0);
        while (findDuplicateSafeState(states)) {
            // System.out.printf("Removing duplicate safe states (%d, %d)\n", states.first,
            // states.second);
            removeSafeState(states);
        }
    }

    /** Calculate the size of the runtime form of this safe state table. */
    int getSafeTableSize() {
        if (fSafeTable == null) {
            return 0;
        }
        int size =
                RBBIDataWrapper.RBBIStateTable
                        .fHeaderSize; // The header, with no rows to the table.
        int numRows = fSafeTable.size();
        int numCols = fSafeTable.get(0).length;
        boolean use8Bits = numRows <= MAX_STATE_FOR_8BITS_TABLE;

        int rowSize = (use8Bits ? 1 : 2) * (RBBIDataWrapper.NEXTSTATES + numCols);
        size += numRows * rowSize;
        // TODO: there are redundant round-up. Figure out best place, get rid of the rest.
        size = (size + 7) & ~7; // round up to a multiple of 8 bytes
        return size;
    }

    /**
     * Create a RBBIDataWrapper.RBBIStateTable for the safe reverse table.
     * RBBIDataWrapper.RBBIStateTable is similar to struct RBBIStateTable in ICU4C, in
     * common/rbbidata.h
     */
    RBBIDataWrapper.RBBIStateTable exportSafeTable() {
        RBBIDataWrapper.RBBIStateTable table = new RBBIDataWrapper.RBBIStateTable();
        table.fNumStates = fSafeTable.size();
        boolean use8Bits = table.fNumStates <= MAX_STATE_FOR_8BITS_TABLE;
        int numCharCategories = fSafeTable.get(0).length;

        // Size of table size in shorts.
        int rowLen = RBBIDataWrapper.NEXTSTATES + numCharCategories;
        // TODO: tableSize is basically numStates * numCharCategories,
        //       except for alignment padding. Clean up here, and in main exportTable().
        int tableSize =
                (getSafeTableSize()
                        - RBBIDataWrapper.RBBIStateTable.fHeaderSize); // fTable length in bytes.
        if (use8Bits) {
            table.fFlags |= RBBIDataWrapper.RBBI_8BITS_ROWS;
            table.fTable = new char[tableSize];
            table.fRowLen = rowLen; // Row length in bytes.
        } else {
            tableSize /= 2; // fTable length in shorts.
            table.fTable = new char[tableSize];
            table.fRowLen = rowLen * 2; // Row length in bytes.
        }

        for (int state = 0; state < table.fNumStates; state++) {
            short[] rowArray = fSafeTable.get(state);
            int row = state * rowLen;

            for (int col = 0; col < numCharCategories; col++) {
                if (use8Bits) {
                    Assert.assrt(rowArray[col] <= MAX_STATE_FOR_8BITS_TABLE);
                }
                table.fTable[row + RBBIDataWrapper.NEXTSTATES + col] = (char) rowArray[col];
            }
        }
        return table;
    }

    // -----------------------------------------------------------------------------
    //
    //   printSet    Debug function.   Print the contents of a set of Nodes
    //
    // -----------------------------------------------------------------------------

    void printSet(Collection<RBBINode> s) {
        for (RBBINode n : s) {
            RBBINode.printInt(n.fSerialNum, 8);
        }
        System.out.println();
    }

    // -----------------------------------------------------------------------------
    //
    //   printStates    Debug Function.  Dump the fully constructed state transition table.
    //
    // -----------------------------------------------------------------------------

    void printStates() {
        int c; // input "character"
        int n; // state number

        System.out.print("state |           i n p u t     s y m b o l s \n");
        System.out.print("      | Acc  LA    Tag");
        for (c = 0; c < fRB.fSetBuilder.getNumCharCategories(); c++) {
            RBBINode.printInt(c, 4);
        }
        System.out.print("\n");
        System.out.print("      |---------------");
        for (c = 0; c < fRB.fSetBuilder.getNumCharCategories(); c++) {
            System.out.print("----");
        }
        System.out.print("\n");

        for (n = 0; n < fDStates.size(); n++) {
            RBBIStateDescriptor sd = fDStates.get(n);
            RBBINode.printInt(n, 5);
            System.out.print(" | ");

            RBBINode.printInt(sd.fAccepting, 3);
            RBBINode.printInt(sd.fLookAhead, 4);
            RBBINode.printInt(sd.fTagsIdx, 6);
            System.out.print(" ");
            for (c = 0; c < fRB.fSetBuilder.getNumCharCategories(); c++) {
                RBBINode.printInt(sd.fDtran[c], 4);
            }
            System.out.print("\n");
        }
        System.out.print("\n\n");
    }

    /** Debug Function. Dump the fully constructed safe reverse table. */
    void printReverseTable() {
        int c; // input "character"

        System.out.printf("    Safe Reverse Table \n");
        if (fSafeTable == null) {
            System.out.printf("   --- nullptr ---\n");
            return;
        }
        int numCharCategories = fSafeTable.get(0).length;
        System.out.printf("state |           i n p u t     s y m b o l s \n");
        System.out.printf("      | Acc  LA    Tag");
        for (c = 0; c < numCharCategories; c++) {
            System.out.printf(" %2d", c);
        }
        System.out.printf("\n");
        System.out.printf("      |---------------");
        for (c = 0; c < numCharCategories; c++) {
            System.out.printf("---");
        }
        System.out.printf("\n");

        for (int n = 0; n < fSafeTable.size(); n++) {
            short rowArray[] = fSafeTable.get(n);
            System.out.printf("  %3d | ", n);
            System.out.printf("%3d %3d %5d ", 0, 0, 0); // Accepting, LookAhead, Tags
            for (c = 0; c < numCharCategories; c++) {
                System.out.printf(" %2d", rowArray[c]);
            }
            System.out.printf("\n");
        }
        System.out.printf("\n\n");
    }

    // -----------------------------------------------------------------------------
    //
    //   printRuleStatusTable    Debug Function.  Dump the common rule status table
    //
    // -----------------------------------------------------------------------------

    void printRuleStatusTable() {
        int thisRecord = 0;
        int nextRecord = 0;
        int i;
        List<Integer> tbl = fRB.fRuleStatusVals;

        System.out.print("index |  tags \n");
        System.out.print("-------------------\n");

        while (nextRecord < tbl.size()) {
            thisRecord = nextRecord;
            nextRecord = thisRecord + tbl.get(thisRecord).intValue() + 1;
            RBBINode.printInt(thisRecord, 7);
            for (i = thisRecord + 1; i < nextRecord; i++) {
                int val = tbl.get(i).intValue();
                RBBINode.printInt(val, 7);
            }
            System.out.print("\n");
        }
        System.out.print("\n\n");
    }
}
